#
# @lc app=leetcode.cn id=111 lang=python3
#
# [111] 二叉树的最小深度
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def minDepth(self, root: TreeNode) -> int:
        """
        最小深度=min(左子树深度， 右子树深度) + 1
        """
        # 错误解法：忽略了要到叶结点
        # left_depth = self.minDepth(root.left)
        # right_depth = self.minDepth(root.right)
        # return min(left_depth, right_depth) + 1

        # 出口
        if not root:
            return 0

        children = [root.left, root.right]
        # 如果子树都空，返回当前深度
        if not children[0] and not children[1]:
            return 1

        min_depth = float('inf')
        for c in children:
            # 子树存在，则下探到下一层
            if c:
                min_depth = min(self.minDepth(c), min_depth)
        return min_depth + 1

# @lc code=end
